#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <string>
#include <iostream>
#include <map>

using namespace std;

map<string, int> color_map;

const int MAX = 105;
int cost[15][MAX];
int cnt[15];
int flag[110005];
int queue[MAX][110005];
int head[MAX], tail[MAX];

int bag(int c[], int n)
{
	if(!n)
		return 0;


	flag[0] = 1;

	head[0] = tail[0] = 0;
	queue[0][tail[0]++] = 0;

	int sum = 0;
	for(int i = 0;i<n;i++)
	{
		sum += c[i];
	}

	int tmp1, tmp2;
	for(int i = 0;i<n;i++)
	{
		memset(flag, 0, sizeof(flag));
		head[i+1] = tail[i+1] = 0;

		for(;head[i] < tail[i];head[i]++)
		{
			tmp1 = queue[i][head[i]] - c[i];
			tmp2 = queue[i][head[i]] + c[i];

			tmp1 = tmp1 >= 0 ? tmp1 : -tmp1;

			if(!flag[tmp1])
			{
				flag[tmp1] = 1;
				queue[i+1][tail[i+1]++] = tmp1;
			}

			if(!flag[tmp2])
			{
				flag[tmp2] = 1;
				queue[i+1][tail[i+1]++] = tmp2;
			}
		}
	}

	int res = 100000000;
	for(;head[n] < tail[n];head[n]++)
	{
		res = min(queue[n][head[n]], res);
	}
	return res + ((sum - res) >> 1);
}

void solve(int m, int n)
{
	color_map.clear();

	string color;
	for(int i = 0;i<m;i++)
	{
		cin >> color;
		color_map[color] = i;
	}

	int c;
	int index;
	memset(cnt, 0, sizeof(cnt));

	for(int i = 0;i<n;i++)
	{
		cin >> c >> color;
		index = color_map[color];
		cost[index][cnt[index]++] = c;
	}

	int res = 0;
	for(int i = 0;i<(int)color_map.size();i++)
	{
		res += bag(cost[i], cnt[i]);
	}

	cout << res << endl;
}

int main()
{
	freopen("data.in", "r", stdin);
	int m, n;
	while(cin >> m >> n)
	{
		if(!m && !n)
			break;
		solve(m, n);
	}
	return 0;
}
